package dp;

//回溯是条不归路,dp可以过
public class DecodeWays91 {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] dp = new int[s.length()];

        for (int i = 0; i < s.length(); i++) {
            int v = Integer.valueOf(s.substring(i,i+1));
            if (v >= 1 && v <= 26) {
                dp[i] = i - 1 >= 0 ? dp[i - 1] : 1;
            }
            if(i-1>=0){
                int vv = Integer.valueOf(s.substring(i - 1, i+1));
                if (vv >= 10 && vv <= 26) {
                    dp[i] = i-2>=0?dp[i] + dp[i - 2]:dp[i]+1;
                }
            }

        }

        return dp[dp.length - 1];
    }


//    public int numDecodings(String s) {
//
//        if (s == null || s.length() == 0) {
//            return 0;
//        }
//
//        return backtracing(0, 1, s);
//    }
//
//    private int backtracing(int begin, int end, String s) {
//        if (begin > end) {
//            return 0;
//        }
//
//        if (end > s.length()) {
//            return 0;
//        }
//
//        Integer v = Integer.parseInt(s.substring(begin, end));
//        if (1 > v || v > 26) {
//            return 0;
//        }
//
//        if (end == s.length()) {
//            return 1;
//        }
//        int count = 0;
//        count += backtracing(begin, end + 1, s);
//        count += backtracing(end, end + 1, s);
//        return count;
//    }
}
